Multiple Planes


You can use multiple planes to get a single hash value. Let's take a look at the following example:

Given some point denoted by v, you can run it through several projections P1,P2,P3P_1, P_2, P_3 to get one hash value. If you compute P1vTP_1v^T you get a positive number, so you set h1=1h_1 =1. P2vTP_2v^T gives you a positive number so you get h2=1h_2 = 1. P3vTP_3v^T is a negative number so you set h3h_3 to be 0. You can then compute the hash value as follows.

hash=20×h1+21×h2+22×h3hash = 2^0 \times h_1 + 2^1 \times h_2 + 2^2 \times h_3

=1×1+2×1+4×0=3 = 1\times 1 + 2 \times 1+ 4 \times 0 = 3

Another way to think of it, is at each time you are asking the plane to which side will you find the point (i.e. 1 or 0) until you find your point bounded by the surrounding planes. The hash value is then defined as:

hashvalue=iH2i×hi hash_value = \sum_i^H 2^i \times h_i

Here is how you can code it up:

P_l is the list of planes. You initialize the value to 0, and then you iterate over all the planes (P), and you keep track of the index. You get the sign by finding the sign of the dot product between v and your plane P. If it is positive you set it equal to 1, otherwise you set it equal to 0. You then add the score for the ith plane to the hash value by computing 2i×hi2^i \times h_i.

 Complete